class Solution {
public:
     const int mode = 1e9+7;
    int cntOfTrees(int n) {
       vector<int> dp(n+1,0);//dp[i]代表节点数为i时呢能够组成多少对的好二叉树。
       dp[0] = 0;
       dp[1] = 1;
       dp[3] = 1;//dp[2]无法构成好二叉树，因为根据好二叉树的定义，只有每个非叶子节点提供2个节点（一定是偶数），但是不要忘了还有一个根节点
       //此时就让节点数量成为了奇数,所以偶数是无法构成好二叉树
       //然后是状态转移方程了,如果节点数量为i，根节点占据一个，左右子树就要从i-1节点进行分配，左子树假设分配k个节点，那么右子树就是i-1-k个节点去进行构
       //造
       if(n%2 == 0)
       {
        return 0;
       }
       for(int i = 5;i<=n;i+=2)
       {
            for(int k = 1;k<i;k+=2)
            {
                dp[i] = (dp[i] + 1LL * dp[k] * dp[i - 1 - k]) % mode;
            }
       }
       return dp[n];
    }
};